1. Field of the Invention
This invention relates to flow control in a packetized data network. In particular, the present invention relates to the calculation of cell transmission rates in an Asynchronous Transfer Mode (ATM) based data network.
2. Description of the Related Art
Data communication under ATM is set forth in a standard entitled "The ATM Forum Specification, version 4.0" (the "ATM standard"). Under the ATM standard, data exchange between a source system and a destination system is accomplished using one or more packetized data streams ("virtual channels"). Data and control information in each virtual channel are transported by 53-byte data packets or cells ("ATM cells"). In general, under the ATM standard, a virtual channel is set up by a virtual circuit connection under a fixed or constant bit rate service (CBR), or a variable bit rate service (VBR). In fact, under the ATM standard, many CBR and VBR virtual circuits can coexist between a given pair of source and destination systems. In one type of VBR service, known as the "available bandwidth rate service" ("ABR service"), the source and destination systems periodically negotiate for each virtual channel a bit rate according to the traffic conditions in all switches along the path of the virtual channel's virtual circuit.
In an ABR virtual circuit, the virtual circuit, the source and destination systems, and all the switches in between, negotiate a "peak cell rate" (PCR), a "minimum cell rate" (MCR), and an "initial cell rate" (ICR). During the life of the virtual circuit, resource management (RM) cells are sent periodically by the source system. Initially, the ATM cells for the virtual channel are sent at the ICR until the first RM cell is sent by the source. Included in the RM cell is an "explicit rate" (ER) field and a "direction" (DIR) field, which are initialized by the source system to the PCR and the value "forward" respectively. Because of the "forward" value in the DIR field, this RM cell is referred to as the "forward RM" (FRM) cell. As the FRM cell traverses the virtual circuit towards the destination system, each switch along the virtual circuit examines the ER field of the FRM cell and, where appropriate, reduces the cell rate specified in that field to indicate the available bandwidth the switch can provide, given its own local traffic condition. If a congestion condition is experienced at the switch, i.e. the instantaneous or immediate rate at which ATM cells are arriving exceeds the rate at which these ATM cells can be processed and forwarded by the switch, a "congestion" field (CI) of the FRM cell is marked. When the FRM cell reaches the destination system, the destination system (i) makes its own adjustment to the ER field, if necessary, (ii) marks the DIR field of the RM cell to indicate that the RM cell is now a "backward" RM (BRM) cell, and (iii) returns the BRM cell to the source system in the reverse direction on the virtual circuit. When the BRM cell reaches the source system, the value in the ER field is examined against the current cell rate. The current cell rate, which is also known as the "allowable cell rate" (ACR), is increased or decreased according to the value in the ER field of the BRM cell returned.
In some applications, e.g. an ATM server, it is necessary to support a very large number of virtual channels (e.g. a 1000 channels) of various fixed and variable bit rates over a given ATM physical media. In such an application, a scheduler coordinates the shared use of the physical media among the large number of virtual channels, so that the use of the physical bandwidth of the physical media can be maximized. In addition, many schedulers provide a "fairness" scheme so that sharing of the available bandwidth among the multiple variable rate virtual channels can be carried out in a predictable manner, and each variable rate virtual channel is given some opportunity to meet its desired cell rate.
One class of fairness schemes is known as the "min-max" fairness schemes. Under a min-max fairness scheme, a system divides the virtual channels into two classes according to their respective cell rates relative to the average cell rater ##EQU1## of the system. In the first class, i.e. those virtual channels having desired cell rates at or below the average cell rate, these virtual channels are provided the desired cell rate. In the second class, i.e. those virtual channels having desired cell rates above the average cell rate, these virtual channels share the remaining bandwidth. Within the second class, the bandwidth can be shared among the virtual channels equally ("unweighted"), or according to some assigned priorities ("weighted"). To ensure robustness under a min-max fairness scheme, the elements in the virtual circuits servicing the virtual channels must be capable of rapid response. Otherwise, data loss may result. For example, consider the case when one congested virtual circuit decreases its cell rate abruptly, thereby relieving the congestion condition at a previously congested element within the virtual circuit. In response to the bandwidth now available at the previous congested element, several virtual circuits may attempt to increase their respective cell rates at the same time. If the readjustment in cell rates in these virtual circuits do not occur rapidly enough, congestion conditions may then reappear at other elements of the network rapidly. Such congestion conditions, if not corrected rapidly, may lead to data loss.